import java.util.ArrayList;

class PriorityQueue {
    ArrayList<Integer> heap;

    //Constructor
    public PriorityQueue() {
        heap = new ArrayList<>();
    }

    public PriorityQueue(int[] qs) {

    }

    //get index of parent leftChild and rightChild
    private int parent(int i) {
        return i / 2;
    }

    private int leftChild(int i) {
        return (2 * i);
    }

    private int rightChild(int i) {

        return ((2 * i) + 1);
    }

    //shiftUp and shiftDown

    private void shiftDown(int i) {
        int maxIndex = i;

        //leftChild
        int lc = leftChild(i);
        if (lc <= heap.size() && heap.get(lc) > heap.get(maxIndex)) {
            maxIndex = lc;
        }

        //right child
        int rc = rightChild(i);
        if (rc <= heap.size() && heap.get(rc) > heap.get(maxIndex)) {
            maxIndex = rc;
        }

        //if i != maxIndex
        if (i != maxIndex) {
            swap(i, maxIndex);
            shiftDown(maxIndex);
        }

    }

    private void swap(int i1, int i2) {
        int temp = heap.get(i1);
        heap.set(i1, heap.get(i2));
        heap.set(i2, temp);
    }

    private void print() {

    }

    //insert
    public void insert(int q) {
        heap.add(q);
        //TODO:if q is the root
        if (heap.size() == 1) return;
        int i = heap.indexOf(q);
        //let p be the parent of q
        int p = heap.get(parent(i));
        while (i > 0 && p <= q) {
            swap(parent(i), i);
            i = parent(i);
        }
    }

    //deleteMin
    public void deleteMin() {


    }

    public void rootFix() {

    }
}

class test_priority_queue {
    public static void main(String[] args) {
        PriorityQueue pq = new PriorityQueue();
        pq.insert(1);
        pq.insert(2);
        pq.insert(45);
        pq.insert(23);
        pq.insert(17);
        System.out.println(pq.heap);


    }
}